package code.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {
    public static void sort(int[] a, int n){
        if (n <= 1) return;
        for (int i = 0; i < n; ++i) {
            //提前退出标志
            boolean flag = true;
            for (int j = 0; j < n - i - 1; ++j) {
                if (a[j] > a[j + 1]) { // 交换
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;

                    //有数据交换
                    flag = false;
                }
            }
            //不存在数据交换，可以提前退出
            if (flag) break;
        }
    }

    /**
     * 冒泡排序改进版
     * 在每一轮排序后记录最后一次元素交换的位置,作为下次比较的边界,
     * 对于边界外的元素在下次循环中无需比较.
     * @param a
     * @param n
     */
    public static void sort2(int[] a, int n){
        if (n <= 1) return;
        //标记最后一次交换的位置
        int lastIndex = n;
        for (int i = 0; i < lastIndex; ++i) {
            //提前退出标志
            boolean flag = true;
            for (int j = 0; j < n - i - 1; ++j) {
                if (a[j] > a[j + 1]) { // 交换
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;

                    //有数据交换
                    flag = false;

                    //标记最后一次交互的位置
                    lastIndex = j;
                }
            }
            //不存在数据交换，可以提前退出
            if (flag) break;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 2, 1, 5, 6, 7, 8};
        sort(array, array.length);
        System.out.println(Arrays.toString(array));

        int[] array2 = new int[]{3, 4, 2, 1, 5, 6, 7, 8};
        sort(array2, array2.length);
        System.out.println(Arrays.toString(array2));
    }

}
